package com.mashibing.class06;

import java.util.HashMap;

//测试链接：https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal
public class Code05_ConstructBinaryTreeFromPreorderAndInorderTraversal {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    public static TreeNode buildTree(int[] pre,int[] in){
        if (pre==null||in==null||pre.length !=in.length){
            return null;
        }
        return f(pre,0, pre.length-1,in,0, in.length-1);
    }
    // 有一棵树, 先序遍历结果是pre[L1...R1], 中序结果是in[L2,R2]
    // 请建出整棵树的回头节点
    public static TreeNode f(int[] pre,int L1, int R1, int[] in, int L2,int R2){
        if (L1 > R1){
            return null;
        }
        TreeNode head = new TreeNode(pre[L1]);
        if (L1==R1){
            return head;
        }
        int find = L2;
        while (in[find]!=pre[L1]) find++;

        head.left=f(pre,L1+1,L1+find-L2,in,L2,find-1);
        head.right=f(pre,L1+find-L2+1,R1,in,find+1,R2);
        return head;
    }

    public static TreeNode buildTree1(int[] pre,int[] in){
        if (pre==null||in==null||pre.length !=in.length){
            return null;
        }

        HashMap<Integer,Integer> valueIndexMap = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            valueIndexMap.put(in[i],i);
        }
        return g(pre,0, pre.length-1,in,0, in.length-1,valueIndexMap);
    }
    // 有一棵树, 先序遍历结果是pre[L1...R1], 中序结果是in[L2,R2]
    // 请建出整棵树的回头节点
    public static TreeNode g(int[] pre,int L1, int R1, int[] in, int L2,int R2,
                             HashMap<Integer,Integer> valueIndexMap){
        if (L1 > R1){
            return null;
        }
        TreeNode head = new TreeNode(pre[L1]);
        if (L1==R1){
            return head;
        }
//        int find = L2;
//        while (in[find]!=pre[L1]) find++;
        int find = valueIndexMap.get(pre[L1]);

        head.left=g(pre,L1+1,L1+find-L2,in,L2,find-1,valueIndexMap);
        head.right=g(pre,L1+find-L2+1,R1,in,find+1,R2,valueIndexMap);
        return head;
    }
}
